<!DOCTYPE html>
            
<HTML>
<HEAD>
<meta name="booktitle" content="Developing Applications With Objective Caml" >
 <meta charset="ISO-8859-1"><meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0">
<META name="GENERATOR" content="hevea 1.05-7 of 2000-02-24">
<META NAME="Author" CONTENT="Christian.Queinnec@lip6.fr">
<LINK rel=stylesheet type="text/css" href="videoc-ocda.css">
<script language="JavaScript" src="videoc.js"><!--
//--></script>
<TITLE>
 Lexicon
</TITLE>
</HEAD>
<BODY class="regularBody">
<A HREF="book-ora104.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora106.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2> Lexicon</H2><A NAME="@concepts221"></A>Lexical analysis is the first step in character string
processing: it segments character strings into a sequence of words
also known as lexical units or lexemes.<BR>
<BR>
<A NAME="toc131"></A>
<H3> Module <TT>Genlex</TT></H3><A NAME="@fonctions347"></A>
<A NAME="@fonctions348"></A>
This module provides a simple primitive allowing the analysis of a string
of characters using several categories of predefined lexical
units. These categories are distinguished by type:<BR>
<BR>


<PRE><BR># <B>type</B><CODE> </CODE>token<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Kwd<CODE> </CODE><B>of</B><CODE> </CODE>string<BR><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Ident<CODE> </CODE><B>of</B><CODE> </CODE>string<BR><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Int<CODE> </CODE><B>of</B><CODE> </CODE>int<BR><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Float<CODE> </CODE><B>of</B><CODE> </CODE>float<BR><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>String<CODE> </CODE><B>of</B><CODE> </CODE>string<BR><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE>Char<CODE> </CODE><B>of</B><CODE> </CODE>char<CODE> </CODE>;;<BR>

</PRE>
<BR>
<BR>
Hence, we will be able to recognize within a character string an
integer (constructor <TT>Int</TT>) and to recover its value
(constructor argument of type <I>int</I>). Recognizable strings and
characters respect the usual conventions: a string is delimited by two
(<TT>"</TT>) characters and character literals by two (<TT>'</TT>)
characters. A float is represented by using either floating-point
notation (for example <EM>0.01</EM>) or exponent-mantissa notation
(for example <EM>1E-2</EM>).<BR>
<BR>
<A NAME="@concepts222"></A><BR>
<BR>
Constructor <TT>Ident</TT> designates the category of
identifiers. These are the names of variables or functions in
programming languages, for example. They comprise all strings of
letters and digits including underscore (<TT>_</TT>) or apostrophe
(<TT>'</TT>). Such a string should not start with a digit. We also consider
as identifiers (for this module at least) strings containing
operator symbols, such as <TT>+</TT>, <TT>*</TT>, <TT>&gt;</TT> or <TT>=</TT>. Finally,
constructor <TT>Kwd</TT> defines the category of keywords containing
distinguished identifiers or special characters (specified by the
programmer when invoking the lexer).<BR>
<BR>
The only variant of the token type controlled by parameters is
that of keywords. The following primitive allows us to create a lexical
analyser (lexer) taking as keywords the list passed as first argument to it.<BR>
<BR>
<A NAME="@fonctions349"></A>


<PRE><BR># Genlex.make_lexer<CODE> </CODE>;;<BR><CODE>- : string list -&gt; char Stream.t -&gt; Genlex.token Stream.t = &lt;fun&gt;</CODE><BR>

</PRE>
<BR>
<BR>
The result of applying <TT>make_lexer</TT> to a list of keywords is a
function taking as input a stream of characters and returning a stream
of lexical units (of type <I>token</I>.)<BR>
<BR>
Thus we can easily obtain a lexer for our BASIC interpreter. We declare the
set of keywords:<BR>
<BR>


<PRE><BR># <B>let</B><CODE> </CODE>keywords<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE>[</CODE><CODE> </CODE><CODE>"REM"</CODE>;<CODE> </CODE><CODE>"GOTO"</CODE>;<CODE> </CODE><CODE>"LET"</CODE>;<CODE> </CODE><CODE>"PRINT"</CODE>;<CODE> </CODE><CODE>"INPUT"</CODE>;<CODE> </CODE><CODE>"IF"</CODE>;<CODE> </CODE><CODE>"THEN"</CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>"-"</CODE>;<CODE> </CODE><CODE>"!"</CODE>;<CODE> </CODE><CODE>"+"</CODE>;<CODE> </CODE><CODE>"-"</CODE>;<CODE> </CODE><CODE>"*"</CODE>;<CODE> </CODE><CODE>"/"</CODE>;<CODE> </CODE><CODE>"%"</CODE>;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>"="</CODE>;<CODE> </CODE><CODE>"&lt;"</CODE>;<CODE> </CODE><CODE>"&gt;"</CODE>;<CODE> </CODE><CODE>"&lt;="</CODE>;<CODE> </CODE><CODE>"&gt;="</CODE>;<CODE> </CODE><CODE>"&lt;&gt;"</CODE>;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>"&amp;"</CODE>;<CODE> </CODE><CODE>"|"</CODE><CODE> </CODE><CODE>]</CODE><CODE> </CODE>;;<BR>

</PRE>
<BR>
<BR>
With this definition in place, we define the lexer:<BR>
<BR>


<PRE><BR># <B>let</B><CODE> </CODE>line_lexer<CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Genlex.make_lexer<CODE> </CODE>keywords<CODE> </CODE><TT>(</TT>Stream.of_string<CODE> </CODE>l<TT>)</TT><CODE> </CODE>;;<BR><CODE>val line_lexer : string -&gt; Genlex.token Stream.t = &lt;fun&gt;</CODE><BR># line_lexer<CODE> </CODE><CODE>"LET x = x + y * 3"</CODE><CODE> </CODE>;;<BR><CODE>- : Genlex.token Stream.t = &lt;abstr&gt;</CODE><BR>

</PRE>

<BR>
<BR>
Function <TT>line_lexer</TT> takes as input a string of characters and
returns the corresponding stream of lexemes. <BR>
<BR>
<A NAME="toc132"></A>
<H3> Use of Streams</H3>
<A NAME="@concepts223"></A>
<A NAME="@concepts224"></A>We can carry out the lexical analysis ``by hand'' by directly
manipulating streams.<BR>
<BR>
The following example is a lexer for arithmetical
expressions. Function <TT>lexer</TT> takes a character stream and
returns a stream of lexical units of type
<I>lexeme Stream.t</I><A NAME="text24" HREF="book-ora111.html#note24"><SUP><FONT SIZE=2>1</FONT></SUP></A>. Spaces, tabs and newline
characters are removed. To simplify, we do not consider variables
or negative integers.<BR>
<BR>
<A NAME="@fonctions350"></A>


<PRE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>spaces<CODE> </CODE>s<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>match</B><CODE> </CODE>s<CODE> </CODE><B>with</B><CODE> </CODE><B>parser</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE>'</CODE><CODE>' '</CODE><CODE> </CODE><CODE> </CODE>;<CODE> </CODE>rest<CODE> </CODE><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>spaces<CODE> </CODE>rest<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE>'</CODE><CODE>'\t'</CODE><CODE> </CODE>;<CODE> </CODE>rest<CODE> </CODE><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>spaces<CODE> </CODE>rest<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE>'</CODE><CODE>'\n'</CODE><CODE> </CODE>;<CODE> </CODE>rest<CODE> </CODE><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>spaces<CODE> </CODE>rest<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>();;<BR><CODE>val spaces : char Stream.t -&gt; unit = &lt;fun&gt;</CODE><BR># <B>let</B><CODE> </CODE><B>rec</B><CODE> </CODE>lexer<CODE> </CODE>s<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE>spaces<CODE> </CODE>s;<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>match</B><CODE> </CODE>s<CODE> </CODE><B>with</B><CODE> </CODE><B>parser</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE><CODE>'</CODE><CODE>'('</CODE><CODE> </CODE><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE>'Lsymbol<CODE> </CODE><CODE>"("</CODE><CODE> </CODE>;<CODE> </CODE>lexer<CODE> </CODE>s<CODE> </CODE><CODE>&gt;]</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE><CODE>'</CODE><CODE>')'</CODE><CODE> </CODE><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE>'Lsymbol<CODE> </CODE><CODE>")"</CODE><CODE> </CODE>;<CODE> </CODE>lexer<CODE> </CODE>s<CODE> </CODE><CODE>&gt;]</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE><CODE>'</CODE><CODE>'+'</CODE><CODE> </CODE><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE>'Lsymbol<CODE> </CODE><CODE>"+"</CODE><CODE> </CODE>;<CODE> </CODE>lexer<CODE> </CODE>s<CODE> </CODE><CODE>&gt;]</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE><CODE>'</CODE><CODE>'-'</CODE><CODE> </CODE><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE>'Lsymbol<CODE> </CODE><CODE>"-"</CODE><CODE> </CODE>;<CODE> </CODE>lexer<CODE> </CODE>s<CODE> </CODE><CODE>&gt;]</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE><CODE>'</CODE><CODE>'*'</CODE><CODE> </CODE><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE>'Lsymbol<CODE> </CODE><CODE>"*"</CODE><CODE> </CODE>;<CODE> </CODE>lexer<CODE> </CODE>s<CODE> </CODE><CODE>&gt;]</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE><CODE>'</CODE><CODE>'/'</CODE><CODE> </CODE><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE>'Lsymbol<CODE> </CODE><CODE>"/"</CODE><CODE> </CODE>;<CODE> </CODE>lexer<CODE> </CODE>s<CODE> </CODE><CODE>&gt;]</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE><CODE>'</CODE><CODE>'0'</CODE><CODE>..</CODE><CODE>'9'</CODE><CODE> </CODE><B>as</B><CODE> </CODE>c;<CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>i<CODE>,</CODE>v<CODE> </CODE><CODE>=</CODE><CODE> </CODE>lexint<CODE> </CODE><TT>(</TT>Char.code<CODE> </CODE>c<CODE> </CODE><CODE>-</CODE><CODE> </CODE>Char.code<TT>(</TT><CODE>'0'</CODE><TT>)</TT><TT>)</TT><CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><CODE>[&lt;</CODE>'Lint<CODE> </CODE>i<CODE> </CODE>;<CODE> </CODE>lexer<CODE> </CODE>v<CODE>&gt;]</CODE><BR><CODE> </CODE><B>and</B><CODE> </CODE>lexint<CODE> </CODE>r<CODE> </CODE>s<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>match</B><CODE> </CODE>s<CODE> </CODE><B>with</B><CODE> </CODE><B>parser</B><CODE> </CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[&lt;</CODE><CODE> </CODE><CODE>'</CODE><CODE>'0'</CODE><CODE>..</CODE><CODE>'9'</CODE><CODE> </CODE><B>as</B><CODE> </CODE>c<CODE> </CODE><CODE>&gt;]</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>-&gt;<CODE> </CODE><B>let</B><CODE> </CODE>u<CODE> </CODE><CODE>=</CODE><CODE> </CODE><TT>(</TT>Char.code<CODE> </CODE>c<TT>)</TT><CODE> </CODE><CODE>-</CODE><CODE> </CODE><TT>(</TT>Char.code<CODE> </CODE><CODE>'0'</CODE><TT>)</TT><CODE> </CODE><B>in</B><CODE> </CODE><CODE> </CODE>lexint<CODE> </CODE><TT>(</TT><CODE>1</CODE><CODE>0</CODE><CODE>*</CODE>r<CODE> </CODE><CODE>+</CODE><CODE> </CODE>u<TT>)</TT><CODE> </CODE>s<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[&lt;&gt;]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>r<CODE>,</CODE>s<BR><CODE> </CODE>;;<BR><CODE>val lexer : char Stream.t -&gt; lexeme Stream.t = &lt;fun&gt;</CODE><BR><CODE>val lexint : int -&gt; char Stream.t -&gt; int * char Stream.t = &lt;fun&gt;</CODE><BR>

</PRE>

<BR>
<BR>
Function <TT>lexint</TT> carries out the lexical analysis for the
portion of a stream describing an integer constant. It is called by
function <TT>lexer</TT> when <TT>lexer</TT> finds a digit on the input stream.
Function <TT>lexint</TT> then consumes all consecutive digits
to obtain the corresponding integer value.<BR>
<BR>
<A NAME="toc133"></A>
<H3> Regular Expressions</H3><A NAME="text25" HREF="book-ora111.html#note25"><SUP><FONT SIZE=2>2</FONT></SUP></A>
<A NAME="@concepts225"></A>
<A NAME="@concepts226"></A><BR>
<BR>
Let's abstract a bit and consider the problem of lexical units from a
more theoretical point of view.<BR>
<BR>
From this point of view, a lexical unit is a word. A word is
formed by concatening items in an alphabet. For our purposes,
the alphabet we are considering is a subset of the ASCII 
characters. Theoretically, a word may contain no characters (the
 empty word<A NAME="text26" HREF="book-ora111.html#note26"><SUP><FONT SIZE=2>3</FONT></SUP></A>) or just a single
character. The theoretical study of the assembly of lexical items 
(lexemes) from members of an alphabet has brought about a simple formalism
known as regular expressions.<BR>
<BR>

<H5> Definition</H5>A regular expression defines a set of words. For example, a regular expression
could specify the set of words that are valid identifiers. 
Regular expressions are specified by a few 
set-theoretic operations. Let <I>M</I> and <I>N</I> be two sets of words. Then
we can specify:
<OL type=1>
<LI>
 the union of <I>M</I> and <I>N</I>, denoted by <I>M</I><FONT SIZE=4><TT> | </TT></FONT><I>N</I>.<BR>
<BR>

<LI> the complement of <I>M</I>, denoted by <FONT SIZE=4><TT>^</TT></FONT><I>M</I>. This 
is the set of all words not in <I>M</I>.<BR>
<BR>

<LI> the concatenation of <I>M</I> and <I>N</I>. This is the set of all the words
formed by placing a word from <I>M</I> before a word from <I>N</I>. We denote
this set simply by <I>MN</I>.<BR>
<BR>

<LI> the set of words formed by a finite sequence of words in <I>M</I>,
denoted <I>M</I><FONT SIZE=4><TT>+</TT></FONT>. <BR>
<BR>

<LI> for syntactic convenience, we write <I>M</I><TT>?</TT> to denote
the set of words in <I>M</I>, with addition of the empty word.
</OL>Individual characters denote the singleton set of words containing
just that character. Expression <TT>a | b | c</TT> thus describes the
set containing
three words: <TT>a</TT>, <TT>b</TT> ant <TT>c</TT>. We will use the more compact
syntax <TT>[abc]</TT> to define such a set. As our alphabet is ordered
(by the ASCII code order) we can also define intervals. For example, the
set of digits can be written: <TT>[0-9]</TT>. We can use parentheses to
group expressions.<BR>
<BR>
If we want to use one of the operator characters as a character in a
regular expression, it should be preceded by the escape character
<TT>\</TT>. For example, <TT>(</TT><TT>\</TT><TT>*)*</TT> denotes the set of sequences of
stars.<BR>
<BR>

<H5> Example</H5> Let's consider the alphabet comprising digits
(<TT>0, 1, 2, 3, 4, 5, 6, 7, 8, 9</TT>) the plus (<TT>+</TT>), minus (<TT>-</TT>) and dot (<TT>.</TT>) signs and letter <TT>E</TT>. We can define the set
<I>num</I> of words denoting numbers. Let's call <I>integers</I> the set defined
with <TT>[0-9]+</TT>. We define the set <I>unum</I> of unsigned numbers
as:<BR><DIV ALIGN=center><TT><I>integers</I></TT><TT>?(.</TT><TT><I>integers</I></TT><TT>)?(E(</TT><TT>\</TT><TT>+|-)?</TT><TT><I>integers</I></TT><TT>)?</TT></DIV><BR>
The set of signed numbers is thus defined as:<BR><DIV ALIGN=center><TT><I>unum</I></TT><TT> | -</TT><TT><I>unum</I></TT> or with <TT>-?<I>unum</I></TT></DIV><BR>

<H5> Recognition</H5>
While regular expressions are a useful formalism in their own right,
we usually wish to implement a program that determines whether a
string of characters (or one of its substrings) is a member of the set
of words described by a regular expression. For that we need to
translate the formal definition of the set into a recognition and
expression processing program. In the case of regular expressions such
a translation can be automated. Such translation techniques are
carried out by module <TT>Genlex</TT> in library <TT>Str</TT>
(described in the next section) and by the <TT>ocamllex</TT> tools that
we introduce in the following two sections.<BR>
<BR>
<A NAME="toc134"></A>
<H3> The <TT>Str</TT> Library</H3>
<A NAME="sec-Str"></A>
<A NAME="@fonctions351"></A>
<A NAME="@fonctions352"></A>
This module contains an abstract data type <I>regexp</I> which
represents regular expressions as well as a function <TT>regexp</TT>
which takes a string describing a regular expression, more or less
following the syntax described above, and returns its abstract
representation.<BR>
<BR>
This module contains, as well, a number of functions which exploit
regular expressions and manipulate strings. The syntax of regular
expressions for library <TT>Str</TT> is given in figure <A HREF="book-ora105.html#fig-str-regexp">11.1</A>.
<BLOCKQUOTE><DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV>
<DIV ALIGN=center>
<TABLE BORDER=1 CELLSPACING=0 CELLPADDING=1>
<TR><TD  VALIGN=top ALIGN=center NOWRAP><CODE>.</CODE></TD>
<TD  VALIGN=top ALIGN=left>any character except <CODE>\n</CODE></TD>
</TR>
<TR><TD  VALIGN=top ALIGN=center NOWRAP><CODE>*</CODE></TD>
<TD  VALIGN=top ALIGN=left>zero or more occurences of the preceding expression</TD>
</TR>
<TR><TD  VALIGN=top ALIGN=center NOWRAP><CODE>+</CODE></TD>
<TD  VALIGN=top ALIGN=left>one or more occurences of the preceding expression</TD>
</TR>
<TR><TD  VALIGN=top ALIGN=center NOWRAP><CODE>?</CODE></TD>
<TD  VALIGN=top ALIGN=left>zero or one occurences of the preceding expression</TD>
</TR>
<TR><TD  VALIGN=top ALIGN=center NOWRAP><CODE>[</CODE>..<CODE>]</CODE></TD>
<TD  VALIGN=top ALIGN=left>set of characters (example <CODE>[abc]</CODE>)</TD>
</TR>
<TR><TD  VALIGN=top ALIGN=center NOWRAP>&nbsp;</TD>
<TD  VALIGN=top ALIGN=left>intervals, denoted by <CODE>-</CODE> (example <CODE>[0-9]</CODE>)</TD>
</TR>
<TR><TD  VALIGN=top ALIGN=center NOWRAP>&nbsp;</TD>
<TD  VALIGN=top ALIGN=left>set complements, denoted by <CODE>^</CODE> (example <CODE>[^A-Z]</CODE>)</TD>
</TR>
<TR><TD  VALIGN=top ALIGN=center NOWRAP><CODE>^</CODE></TD>
<TD  VALIGN=top ALIGN=left>start of line (not to be mistaken with the use of <CODE>^</CODE> as a set
 complement)</TD>
</TR>
<TR><TD  VALIGN=top ALIGN=center NOWRAP><CODE>$</CODE></TD>
<TD  VALIGN=top ALIGN=left>end of line</TD>
</TR>
<TR><TD  VALIGN=top ALIGN=center NOWRAP><CODE>|</CODE></TD>
<TD  VALIGN=top ALIGN=left>alternative</TD>
</TR>
<TR><TD  VALIGN=top ALIGN=center NOWRAP><CODE>(</CODE>..<CODE>)</CODE></TD>
<TD  VALIGN=top ALIGN=left>grouping of a complex expression (we can later refer to such an
expression by an integer index -- see below)</TD>
</TR>
<TR><TD  VALIGN=top ALIGN=center NOWRAP><I>i</I></TD>
<TD  VALIGN=top ALIGN=left>an integer constant, referring to the string matched by the <I>i</I>-th
 complex expression</TD>
</TR>
<TR><TD  VALIGN=top ALIGN=center NOWRAP><CODE>\</CODE></TD>
<TD  VALIGN=top ALIGN=left>escape character (used when matching a reserved character in regular expressions)</TD>
</TR></TABLE>
</DIV>
<BR>
<DIV ALIGN=center>Figure 11.1: Regular expressions<A NAME="fig-str-regexp"></A>.</DIV><BR>

<DIV ALIGN=center><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<H5> Example</H5> We want to write a function translating dates in
anglo-saxon format into French dates within a data file. We suppose
that the file is organised into lines of data fields and the
components of an anglo-saxon date are separated by dots. Let's define
a function which takes as argument a string (i.e. a line
from the file), isolates the date, decomposes and translates it, then
replaces the original with the translation.
<A NAME="@fonctions353"></A>
<A NAME="@fonctions354"></A>
<A NAME="@fonctions355"></A>


<PRE><BR># <B>let</B><CODE> </CODE>french_date_of<CODE> </CODE>d<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE><B>match</B><CODE> </CODE>d<CODE> </CODE><B>with</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[</CODE>mm;<CODE> </CODE>dd;<CODE> </CODE>yy<CODE>]</CODE><CODE> </CODE>-&gt;<CODE> </CODE>dd<CODE>^</CODE><CODE>"/"</CODE><CODE>^</CODE>mm<CODE>^</CODE><CODE>"/"</CODE><CODE>^</CODE>yy<BR><CODE> </CODE><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>_</CODE><CODE> </CODE>-&gt;<CODE> </CODE>failwith<CODE> </CODE><CODE>"Bad date format"</CODE><CODE> </CODE>;;<BR><CODE>val french_date_of : string list -&gt; string = &lt;fun&gt;</CODE><BR><BR># <B>let</B><CODE> </CODE>english_date_format<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Str.regexp<CODE> </CODE><CODE>"[0-9]+\.[0-9]+\.[0-9]+"</CODE><CODE> </CODE>;;<BR><CODE>val english_date_format : Str.regexp = &lt;abstr&gt;</CODE><BR><BR># <B>let</B><CODE> </CODE>trans_date<CODE> </CODE>l<CODE> </CODE><CODE>=</CODE><CODE> </CODE><BR><CODE> </CODE><CODE> </CODE><B>try</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>i<CODE>=</CODE>Str.search_forward<CODE> </CODE>english_date_format<CODE> </CODE>l<CODE> </CODE><CODE>0</CODE><CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>d1<CODE> </CODE><CODE>=</CODE><CODE> </CODE>Str.matched_string<CODE> </CODE>l<CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><B>let</B><CODE> </CODE>d2<CODE> </CODE><CODE>=</CODE><CODE> </CODE>french_date_of<CODE> </CODE><TT>(</TT>Str.split<CODE> </CODE><TT>(</TT>Str.regexp<CODE> </CODE><CODE>"\."</CODE><TT>)</TT><CODE> </CODE>d1<TT>)</TT><CODE> </CODE><B>in</B><BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>Str.global_replace<CODE> </CODE>english_date_format<CODE> </CODE>d2<CODE> </CODE>l<BR><CODE> </CODE><CODE> </CODE><B>with</B><CODE> </CODE>Not_found<CODE> </CODE>-&gt;<CODE> </CODE>l<CODE> </CODE>;;<BR><CODE>val trans_date : string -&gt; string = &lt;fun&gt;</CODE><BR><BR># trans_date<CODE> </CODE><CODE>"..............06.13.99............"</CODE><CODE> </CODE>;;<BR><CODE>- : string = "..............13/06/99............"</CODE><BR>

</PRE>
<BR>
<BR>
<A NAME="toc135"></A>
<H3> The <TT>ocamllex</TT> Tool</H3>
<A NAME="@fonctions356"></A>
<A NAME="@concepts227"></A>
<A NAME="@fonctions357"></A>
<A NAME="@fonctions358"></A>
<A NAME="@concepts228"></A>
The <TT>ocamllex</TT> tool is a lexical analyzer generator built for Objective CAML
after the model of the <TT>lex</TT> tool for the C language. It generates
a source Objective CAML file from a file describing the lexical elements to
be recognized in the form of regular expressions. The programmer can
augment each lexical element description with a processing action known
as a semantic action. The generated code manipulates an abstract
type <I>lexbuf</I> defined in module <TT>Lexing</TT>. The
programmer can use this module to control processing of lexical
buffers.
<BR>
<BR>
Usually the lexical description files are given the extension
<TT>.mll</TT>. Later, to obtain a Objective CAML source from a <TT>lex_file.mll</TT>
 you type the command
<PRE>
ocamllex lex_file.mll
</PRE>A file <TT>lex_file.ml</TT> is generated containing the code for the
corresponding analyzer. This file can then be compiled with other
modules of an Objective CAML application. For each set of lexical analysis
rules there is a corresponding function taking as input a lexical
buffer (of type <I>Lexing.lexbuf</I>) and returning the value
defined by the semantic actions. Consequently, all actions in the same
rule must produce values of the same type.<BR>
<BR>
The general format for an <TT>ocamllex</TT> file is<BR>
<BR>
<TABLE CELLSPACING=0 CELLPADDING=0>
<TR><TD  ALIGN=left NOWRAP><TT>{</TT></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP></TD>
<TD  ALIGN=left NOWRAP>header</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP><TT>}</TT></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP><B>let</B> ident <TT>=</TT> regexp</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP></TD>
<TD  ALIGN=left NOWRAP>...</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP><B>rule</B> ruleset1 <TT>=</TT> <B>parse</B></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP></TD>
<TD  ALIGN=left NOWRAP></TD>
<TD  ALIGN=left NOWRAP>  regexp <TT>{</TT> action <TT>}</TT></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP></TD>
<TD  ALIGN=left NOWRAP></TD>
<TD  ALIGN=left NOWRAP><TT>|</TT> ...</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP></TD>
<TD  ALIGN=left NOWRAP></TD>
<TD  ALIGN=left NOWRAP><TT>|</TT> regexp <TT>{</TT> action <TT>}</TT></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP><B>and</B> ruleset2 <TT>=</TT> <TT>parse</TT></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP></TD>
<TD  ALIGN=left NOWRAP></TD>
<TD  ALIGN=left NOWRAP>...</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP><B>and</B> ...</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP><TT>{</TT></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP></TD>
</TR>
<TR><TD  ALIGN=left NOWRAP></TD>
<TD  ALIGN=left NOWRAP>trailer-and-end</TD>
</TR>
<TR><TD  ALIGN=left NOWRAP><TT>}</TT> 
</TD>
</TR></TABLE><BR>
Both section ``header'' and ``trailer-and-end'' are optional. They
contain Objective CAML code defining types, functions, etc.&nbsp;needed for
processing. The code in the last section can use the lexical analysis
functions that will be generated by the middle section. The
declaration list preceding the rule definition allows the user to give
names to some regular expressions. They can later be invoked by name
in the definition of rules.<BR>
<BR>

<H5> Example</H5><A NAME="basic-lex1"></A> Let's revisit our BASIC
example. We will want to refine the type of lexical units
returned. We will once again define function <TT>lexer</TT>
(as we did on page <A HREF="book-ora058.html#basic-lex0">??</A>) with the same type of output 
(<I>lexeme</I>), but taking as input a buffer of type 
<I>Lexing.lexbuf</I>.<BR>
<BR>


<PRE><BR>{<BR><CODE> </CODE><B>let</B><CODE> </CODE>string_chars<CODE> </CODE>s<CODE> </CODE><CODE>=</CODE><BR><CODE> </CODE><CODE> </CODE>String.sub<CODE> </CODE>s<CODE> </CODE><CODE>1</CODE><CODE> </CODE><TT>(</TT><TT>(</TT>String.length<CODE> </CODE>s<TT>)</TT><CODE>-</CODE><CODE>2</CODE><TT>)</TT><CODE> </CODE>;;<BR>}<BR><BR><B>let</B><CODE> </CODE>op_ar<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>[</CODE><CODE>'-'</CODE><CODE> </CODE><CODE>'+'</CODE><CODE> </CODE><CODE>'*'</CODE><CODE> </CODE><CODE>'%'</CODE><CODE> </CODE><CODE>'/'</CODE><CODE>]</CODE><BR><B>let</B><CODE> </CODE>op_bool<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>[</CODE><CODE>'!'</CODE><CODE> </CODE><CODE>'&amp;'</CODE><CODE> </CODE><CODE>'|'</CODE><CODE>]</CODE><CODE> </CODE><BR><B>let</B><CODE> </CODE>rel<CODE> </CODE><CODE>=</CODE><CODE> </CODE><CODE>[</CODE><CODE>'='</CODE><CODE> </CODE><CODE>'&lt;'</CODE><CODE> </CODE><CODE>'&gt;'</CODE><CODE>]</CODE><BR><BR>rule<CODE> </CODE>lexer<CODE> </CODE><CODE>=</CODE><CODE> </CODE>parse<BR><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE>[</CODE><CODE>' '</CODE><CODE>]</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>{<CODE> </CODE>lexer<CODE> </CODE>lexbuf<CODE> </CODE>}<BR><BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE>op_ar<CODE> </CODE><CODE> </CODE><CODE> </CODE>{<CODE> </CODE>Lsymbol<CODE> </CODE><TT>(</TT>Lexing.lexeme<CODE> </CODE>lexbuf<TT>)</TT><CODE> </CODE>}<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE>op_bool<CODE> </CODE>{<CODE> </CODE>Lsymbol<CODE> </CODE><TT>(</TT>Lexing.lexeme<CODE> </CODE>lexbuf<TT>)</TT><CODE> </CODE>}<BR><BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"&lt;="</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>{<CODE> </CODE>Lsymbol<CODE> </CODE><TT>(</TT>Lexing.lexeme<CODE> </CODE>lexbuf<TT>)</TT><CODE> </CODE>}<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"&gt;="</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>{<CODE> </CODE>Lsymbol<CODE> </CODE><TT>(</TT>Lexing.lexeme<CODE> </CODE>lexbuf<TT>)</TT><CODE> </CODE>}<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"&lt;&gt;"</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>{<CODE> </CODE>Lsymbol<CODE> </CODE><TT>(</TT>Lexing.lexeme<CODE> </CODE>lexbuf<TT>)</TT><CODE> </CODE>}<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE>rel<CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>{<CODE> </CODE>Lsymbol<CODE> </CODE><TT>(</TT>Lexing.lexeme<CODE> </CODE>lexbuf<TT>)</TT><CODE> </CODE>}<BR><BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"REM"</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>{<CODE> </CODE>Lsymbol<CODE> </CODE><TT>(</TT>Lexing.lexeme<CODE> </CODE>lexbuf<TT>)</TT><CODE> </CODE>}<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"LET"</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>{<CODE> </CODE>Lsymbol<CODE> </CODE><TT>(</TT>Lexing.lexeme<CODE> </CODE>lexbuf<TT>)</TT><CODE> </CODE>}<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"PRINT"</CODE><CODE> </CODE>{<CODE> </CODE>Lsymbol<CODE> </CODE><TT>(</TT>Lexing.lexeme<CODE> </CODE>lexbuf<TT>)</TT><CODE> </CODE>}<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"INPUT"</CODE><CODE> </CODE>{<CODE> </CODE>Lsymbol<CODE> </CODE><TT>(</TT>Lexing.lexeme<CODE> </CODE>lexbuf<TT>)</TT><CODE> </CODE>}<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"IF"</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>{<CODE> </CODE>Lsymbol<CODE> </CODE><TT>(</TT>Lexing.lexeme<CODE> </CODE>lexbuf<TT>)</TT><CODE> </CODE>}<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>"THEN"</CODE><CODE> </CODE><CODE> </CODE>{<CODE> </CODE>Lsymbol<CODE> </CODE><TT>(</TT>Lexing.lexeme<CODE> </CODE>lexbuf<TT>)</TT><CODE> </CODE>}<BR><CODE> </CODE><BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'-'</CODE><CODE>?</CODE><CODE> </CODE><CODE>[</CODE><CODE>'0'</CODE><CODE>-</CODE><CODE>'9'</CODE><CODE>]+</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>{<CODE> </CODE>Lint<CODE> </CODE><TT>(</TT>int_of_string<CODE> </CODE><TT>(</TT>Lexing.lexeme<CODE> </CODE>lexbuf<TT>)</TT><TT>)</TT><CODE> </CODE>}<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>[</CODE><CODE>'A'</CODE><CODE>-</CODE><CODE>'z'</CODE><CODE>]+</CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE><CODE> </CODE>{<CODE> </CODE>Lident<CODE> </CODE><TT>(</TT>Lexing.lexeme<CODE> </CODE>lexbuf<TT>)</TT><CODE> </CODE>}<BR><CODE> </CODE><CODE>|</CODE><CODE> </CODE><CODE>'"'</CODE><CODE> </CODE><CODE>[</CODE><CODE>^</CODE><CODE> </CODE><CODE>'"'</CODE><CODE>]*</CODE><CODE> </CODE><CODE>'"'</CODE><CODE> </CODE><CODE> </CODE>{<CODE> </CODE>Lstring<CODE> </CODE><TT>(</TT>string_chars<CODE> </CODE><TT>(</TT>Lexing.lexeme<CODE> </CODE>lexbuf<TT>)</TT><TT>)</TT><CODE> </CODE>}<BR>

</PRE>
<BR>
<BR>
The translation of this file by <TT>ocamllex</TT> returns function
<TT>lexer</TT> of type <I>Lexing.lexbuf -&gt; lexeme</I>. We will
see later how to use such a function in conjunction with syntactic
analysis (see page <A HREF="book-ora106.html#sec-join-alex">??</A>).<BR>
<BR>
<HR>
<A HREF="book-ora104.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="index.html"><IMG SRC ="contents_motif.gif" ALT="Contents"></A>
<A HREF="book-ora106.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
